#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int minExtraChar(string s, vector<string>& dictionary) {
        int len = s.size();
        int n = dictionary.size();
        vector<int> dp(len + 1);
        for (int i = 1; i <= len; i++)dp[i] = i;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < n; j++) {
                if (dictionary[j].size() > i + 1)continue;
                int m = dictionary[j].size();
                string res = s.substr(i - m + 1, m);
                if (res == dictionary[j])dp[i + 1] = min(dp[i - m + 1], dp[i + 1]);
            }
            dp[i + 1] = min(dp[i + 1], dp[i] + 1);
        }
        return dp[len];
    }
};